﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphLibrary.Algorithms
{
    sealed public class Coloring<TVertex, TEdge> : GraphAlgorithm<TVertex, TEdge>
        where TEdge : IEdge<TVertex>
    {
        private Dictionary<TVertex, GraphColor> _colors = new Dictionary<TVertex, GraphColor>();

        private int _colorNumber;

        public Coloring(IUndirectedGraph<TVertex,TEdge> graph)
        {
            Graph = graph;
        }

        public int ChromaticNumber
        {
            get
            {
                return _colorNumber;
            }
        }

        public Dictionary<TVertex, GraphColor> Colors
        {
            get
            {
                return _colors;
            }

        }

        public void Execute()
        {
            _colorNumber = 0;
            // вершины, соседние с вершинами, раскрашенными текущим цветом
            List<TVertex> restrictedVertices = new List<TVertex>();
            // пока все не окрашены
            while (_colors.Count != Graph.CountOfVertices)
            {
                restrictedVertices.Clear();
                foreach (TVertex vertex in Graph.Vertices)
                {
                    GraphColor color = (GraphColor)_colorNumber;
                    if (!_colors.ContainsKey(vertex) && !restrictedVertices.Contains(vertex))
                    {
                        _colors.Add(vertex, color); // раскраска вершины
                        //_colors[vertex] = color;
                        restrictedVertices.AddRange(Graph.AdjacentVertices(vertex));
                    }
                }
                _colorNumber++;
            }
        }
    }
}
